package oop.ex4.search;

import java.util.Date;
import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.FutureTask;

/**
 * An implementation of a Depth Limited Search for SearchBoards.
 * Based on a while loop and a stack, instead of an iterator.
 *   
 * @author yomach
 * @author mbattat
 * 
 * @param <B> The search board.
 * @param <M> The search moves.
 */
public class MyDepthFirstSearch<B extends SearchBoard<M>,M extends SearchMove> implements DepthFirstSearch<B, M> {
	
	///////////////////////////////////////////////////////
	/////////////////////Public Method/////////////////////
	///////////////////////////////////////////////////////
	
	@SuppressWarnings("unchecked")
	@Override
	public B search(B board, int maxDepth, long timeOut) {
		FutureTask<B> bestSearch = new FutureTask<B>(new MyBestDepthSearch<B,M>(board, maxDepth));
		long maxTime = new Date().getTime() + timeOut;
		B bestBoard =  (B) board.getCopy();
		if (board.getQualityBound() < 0) { return null; }
		Deque<LastIterator<M>> iteratorStack = new LinkedList<LastIterator<M>>();
		LastIterator<M> iterator = new LastIterator<M>(board.getMoveIterator());
		while (new Date().getTime() <= maxTime) {
			if (bestSearch != null && bestSearch.isDone()) {
				try {
					if (bestSearch.get() != null) { return bestSearch.get(); }
					else { bestSearch = null; }
				} catch (InterruptedException e) {
					bestSearch = null;
				} catch (ExecutionException e) {
					bestSearch = null;
				}
			}
			if (!iterator.hasNext() || maxDepth == 0) { // Depth limit or no more moves.
				if (iteratorStack.isEmpty()) { 
					break;
				} // No more moves at all.
				maxDepth++;
				iterator = iteratorStack.pop();
				board.undoMove(iterator.last());
				continue;
			}
			M move = iterator.next();
			board.doMove(move);
			if (board.getQualityBound() <= bestBoard.getQuality()) { // This branch cannot improve quality.
				board.undoMove(iterator.last());
				continue;
			}
			if (board.isBestSolution()) { // This branch hits the jackpot.
				return board;
			}
			if (board.getQuality() > bestBoard.getQuality()) { // Initial bestBoard quality is -1.
				bestBoard = (B) board.getCopy();
			}
			maxDepth--;
			iteratorStack.push(iterator);
			iterator = new LastIterator<M>(board.getMoveIterator());
		}
		if (bestBoard.getQuality() < 0) { return null; }
		return bestBoard;
	}
	
	///////////////////////////////////////////////////////
	/////////////////////Nested Classes////////////////////
	///////////////////////////////////////////////////////	
	
	/**
	 * A nested decorator class of the iterator that allows retrieval of the
	 * last item.
	 *
	 * @author yomach
	 * @author mbattat
	 *
	 * @param <K> The Iterator type.
	 */
	public static class LastIterator<K> implements Iterator<K> {

		///////////////////////////////////////////////////////
		/////////////////////Data members//////////////////////
		///////////////////////////////////////////////////////
		
		/**
		 * The iterator.
		 */
		private Iterator<K> _iterator;
		
		/**
		 * The last item.
		 */
		private K _last;
		
		
		///////////////////////////////////////////////////////
		/////////////////////Constructors//////////////////////
		///////////////////////////////////////////////////////
		
		/**
		 * Creates a new Last Iterator with the given iterator.
		 * @param iterator The iterator.
		 */
		public LastIterator(Iterator<K> iterator) {
			_iterator = iterator;
			_last = null;
		}
		
		///////////////////////////////////////////////////////
		////////////////////Public Methods/////////////////////
		///////////////////////////////////////////////////////
		
		@Override
		public boolean hasNext() {
			return _iterator.hasNext();
		}

		@Override
		public K next() {
			return _last = _iterator.next();
		}

		@Override
		public void remove() {
			_iterator.remove();
		}
		
		/**
		 * Returns the last element again. <br>
		 * Calling last() before the first time next() has been called will return null.
		 * @return The last element again.
		 */
		public K last() {
			return _last;
		}
	}
}